package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.List;
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * @author shiminghui
 * @date 2025/3/15 15:26
 * @description: TODO
 */
public class _047_图_prim算法 {

    @Test
    public void test1() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");


        v1.setEdges(List.of(new Edge(v1, v3, 1), new Edge(v1, v6, 1)));
        v2.setEdges(List.of(new Edge(v2, v3, 1)));
        v3.setEdges(List.of(new Edge(v3, v4, 1), new Edge(v3, v2, 1), new Edge(v3, v1, 1)));
        v4.setEdges(List.of(new Edge(v4, v5, 1), new Edge(v4, v3, 1)));
        v5.setEdges(List.of(new Edge(v5, v6, 1), new Edge(v5, v4, 1)));
        v6.setEdges(List.of(new Edge(v6, v1, 1), new Edge(v6, v5, 1)));
        prim(List.of(v1, v2, v3, v4, v5, v6));
    }

    private void prim(List<Vertex> vertexs) {
        Vertex v = vertexs.get(0); // 作为起始顶点
        PriorityQueue<Vertex> minHeap = new PriorityQueue<>(Comparator.comparingInt(Vertex::getDistance));
        v.setDistance(0);
        minHeap.offer(v);
        while (!minHeap.isEmpty()) {
            Vertex vertex = minHeap.poll();
            if (vertex.isVisited()) { // 如果已经处理过,跳过
                continue;
            }
            vertex.setVisited(true);
            List<Edge> edges = vertex.getEdges();
            if (edges == null) {
                continue;
            }
            for (Edge edge : edges) {
                Vertex edgeTo = edge.getTo();
                if (edge.getWeight() < edgeTo.getDistance()) {
                    edgeTo.setDistance(edge.getWeight());
                    edgeTo.setPre(vertex);
                    minHeap.add(edgeTo); // 这里必须加入,因为不加入,minHeap中不会自动排序,之后加一个是否访问的判断
                }
            }
        }
        for (Vertex vertex : vertexs) {
            if (vertex != v) {
                System.out.println(vertex.getName() + "-->" + vertex.getPre().getName() + ":" + vertex.getDistance());
            }
        }
    }


    private class Vertex {
        private String name;
        private int status;
        private List<Edge> edges;
        private int inDegree; // 入度
        private boolean isVisited; // 是否访问过
        private int distance; // 到该顶点的最短路径
        private Vertex pre; // 记录该顶点的前驱顶点

        { // 初始化
            status = 0;
            distance = Integer.MAX_VALUE;
            isVisited = false;
            inDegree = 0;
        }

        public Vertex(String name) {
            this.name = name;
        }

        public Vertex(String name, List<Edge> edges) {
            this.name = name;
            this.edges = edges;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex vertex = (Vertex) o;
            return status == vertex.status && inDegree == vertex.inDegree && isVisited == vertex.isVisited && distance == vertex.distance && Objects.equals(name, vertex.name) && Objects.equals(edges, vertex.edges) && Objects.equals(pre, vertex.pre);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }

        public Vertex getPre() {
            return pre;
        }

        public void setPre(Vertex pre) {
            this.pre = pre;
        }

        public boolean isVisited() {
            return isVisited;
        }

        public void setVisited(boolean visited) {
            isVisited = visited;
        }

        public int getDistance() {
            return distance;
        }

        public void setDistance(int distance) {
            this.distance = distance;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getStatus() {
            return status;
        }

        public void setStatus(int status) {
            this.status = status;
        }

        public List<Edge> getEdges() {
            return edges;
        }

        public void setEdges(List<Edge> edges) {
            this.edges = edges;
        }

        public int getInDegree() {
            return inDegree;
        }

        public void setInDegree(int inDegree) {
            this.inDegree = inDegree;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "name='" + name + '\'' +
                    '}';
        }
    }

    private class Edge {
        private Vertex from;
        private Vertex to;
        private int weight;

        public Edge(Vertex from, Vertex to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Vertex getFrom() {
            return from;
        }

        public void setFrom(Vertex from) {
            this.from = from;
        }

        public Vertex getTo() {
            return to;
        }

        public void setTo(Vertex to) {
            this.to = to;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }
}
